package cn.wgx.study.algorithm;

import java.util.Arrays;

/**
 * 希尔排序
 */
public class Shell extends SortBase {

    public static void main(String[] args) {
//        int[] array = generate(100, 100);
        int[] array = {99, 45, 75, 84, 24, 72, 69, 51, 90, 93, 97, 19, 99, 36, 10, 12, 54, 37, 44, 14, 60, 29, 77, 60, 81, 65, 65, 49, 53, 71, 40, 20, 27, 90, 12, 43, 49, 17, 70, 80, 68, 21, 61, 19, 47, 28, 90, 38, 94, 81, 75, 6, 0, 64, 63, 64, 94, 38, 13, 62, 5, 67, 73, 36, 0, 22, 67, 82, 70, 8, 66, 43, 30, 11, 25, 60, 88, 69, 18, 80, 93, 76, 69, 5, 56, 10, 96, 4, 83, 67, 99, 9, 9, 63, 69, 10, 17, 6, 99, 89};
        int[] array1 = Arrays.copyOf(array, array.length);
        int[] array2 = Arrays.copyOf(array, array.length);
        int[] array3 = Arrays.copyOf(array, array.length);
        print(array);

        print(sort3(array1));
//        print(shell(array, 1, 0));
//        print(Insertion.sort(array3));
        Arrays.sort(array2);

        print(array2);
        System.out.println(compare(array1, array2));
    }

    //shell2
    public static int[] sort(int array[]) {
        int swapN = 0, len = array.length, m = len / 3;
        int h = 1;//Knuth算法
        while(h <= m){
            h = 3*h+1;
        }
//        for (int step = h; step > 0; step=(step-1)/3) {
        for (int step = h; step > 0; step=step/2) {
            for (int i = step; i < len &&  i > step -1; i++) {
                if (array[i] < array[i - step]) {
                    int tmp = array[i];
                    int j = i;
                    for (; j > step - 1; j -= step) {
                        if (tmp < array[j - step]) {
                            swapN++;
                            array[j] = array[j - step];
                        } else break;
                    }
                    array[j] = tmp;
                }
            }
        }
        System.out.println("希尔次数: " + swapN);
        return array;
    }

    //希尔排序
    public static int[] sort2(int array[]) {

        int step = array.length / 50, s = 0, n = 0;
        while (s < step) {
            n += shell(array, step, s++);
        }
        n += shell(array, 1, 0);
        System.out.println("希尔次数" + n);
        return array;
    }

    //希尔排序
    public static int[] sort3(int array[]) {

        int step = array.length / 20, s = step, n = 0;
        while (s >= 0) {
            n += shell(array, step, step-(s--));
        }
        //n += shell(array, 1, 0);
        System.out.println("希尔次数" + n);
        return array;
    }

    /**
     * @param array
     * @param step  步长
     * @param s     起始位置
     * @return
     */
    private static int shell(int array[], int step, int s) {
        int swapNum = 0;
        for (int i = s + step, n = array.length; i < n; i += step) {
            if (array[i] < array[i - step]) {
                int tmp = array[i];
                int j = i;
                for (; j > (step - 1); j -= step) {
                    if (tmp < array[j - step]) {
                        array[j] = array[j - step];
                        swapNum++;
                    } else break;
                }
                array[j] = tmp;
            }
        }
        return swapNum;
    }


}
